/*
提交链接：https://leetcode.cn/problems/kth-missing-positive-number/description/
1539. 第 k 个缺失的正整数-简单
完成日期：2024/9/14
二分搜索
*/

class Solution {
public:
    // 函数 findKthPositive 用于找到第 k 个缺失的正整数
    int findKthPositive(vector<int>& a, int k) {
        int n = a.size(); // 获取数组 a 的大小

        // 如果数组的第一个元素大于 k，说明前 k 个正整数都是缺失的
        if(a[0] > k) return k;

        int l = 0, r = n - 1; // 初始化左右指针

        // 使用二分查找来寻找第 k 个缺失的正整数
        while(l < r) {
            int mid = ((r - l + 1) >> 1) + l; // 计算中间位置

            // 判断 mid 位置之前缺失的正整数数量是否小于 k
            if(a[mid] - mid - 1 < k) 
                l = mid; // 如果缺失数量小于 k，向右移动左指针
            else 
                r = mid - 1; // 否则，向左移动右指针
        }

        // 返回缺失的第 k 个正整数
        return k - (a[l] - l - 1) + a[l];
    }
};